<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>STtable</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">ST表</h1>
<p>ST表：全称为SparseTable，意为稀疏表。适用于求一些区间内的最大值、最小值、gcd、delta等操作。</p>
<h4 id="toc-1">ST表思路：</h4>
<p>ST表的是一种基于动态规划的方法，对于f[i][j]而言，记录的是区间[i,i+(1&lt;&lt;j)-1]区间的值，其中要初始化f[i][0]=a[i]。</p>
<p>所以对于任意一组i、j，f(i,j)=min{f(i,j-1),f(i+1&lt;&lt;(j-1)+j-1}而通过动态规划计算出来。</p>
<h4 id="toc-2">ST表特点</h4>
<p>用nlogn的时间复杂度建立ST表，然后以O（1）查询</p>
<p>假设我们要求区间[m,n]的极值，找到一个数k使得(1&lt;&lt;k)&lt;n-m+1。</p>
<p>即</p>
<p>[k=[\frac{ln(n-m+1)}{ln(2)} ]]</p>
<p>可以把这个区间分成两部分，[m,m+(1&lt;&lt;k)-1]和[n-(1&lt;&lt;k)+1,n]两个部分，并且，这两个部分是已经初始化、预处理好了的，前面的区间就是f(m,m+(1&lt;&lt;k)-1)，后面的区间就是f(n-(1&lt;&lt;k)+1,n)，那么只用考虑着两个区间的值就好了。</p>
<p>同时我们把这一类问题称之为RMQ问题，区间最值查询问题。</p>
<p>RMQ问题：对于一个长度为n的数列A，每次询问回答i-j区间的在数列A中的最值</p>
<p>同时ST表是离线问题，因为ST表一旦改变了，那这个表都得重新建立，当然不妨碍ST表在线查询。</p>
<h4 id="toc-3">ST表的核心</h4>
<p>ST表主要是依据倍增算法来的，可以很形象的理解为天平秤东西的时候放砝码，都是要尽可能从大的去放，st表也是一样，第一次尽可能选择大的，就从极大值开始找了，从大到小去试=。=</p>
<pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
const int maxn=1e6+7;
int st[maxn][32];
int a[maxn],n;
void init(){
    int i,j;
    //st[i][j]表示i到i+2^j-1区间的最小值
    //先预处理区间长度为1的
    for(i=0;i&lt;n;++i)  st[i][0]=a[i];
    for(i=0;i&lt;n;++i){
        for(j=1;i+(1&lt;&lt;j)-1&lt;n;++j){//这里有一个优化。。本来是小于32的。。问题规模较小是只是相当于一个常数的优化 
            //i~i+2^(j-1)-1
            //i+2^(j-1)~i+2^(j-1)+2^(j-1)-1=&gt;i+2^j-1;
            //一定要发现这个显然的事实就是
            //2^(j-1)+2^(j-1)=2^j; 
            st[i][j]=min(st[i][j-1],st[i+(1&lt;&lt;(j-1))][j-1]);
        }
    }
}
int queryMin(int l,int r){
    int k=log(r-l+1);
    //st[l][index] l~l+2^(index)-1
    //2^(index)&lt;=(r-l+1); l+2^(index)-1&lt;=r
    //r-(l+2^(index)-1)&gt;=0 还差多少元素没放进来
    //x+LEN=l+2^(index)-1+(r-(l+2^(index)-1));
    //x+2^(index)-1=r;//区间长度固定。。起点是多少才能正好跑到r,列一个简单的方程才能解决 
    //x=r+1-(2^(index));
    return min(st[l][k],st[r+1-(1&lt;&lt;k)][k]);
}
int main(){
    while(~scanf("%d",&amp;n)){
        int i,q,l,r;
        for(i=0;i&lt;n;++i){
            scanf("%d",a+i);
        }
        init();
        scanf("%d",&amp;q);
        for(i=0;i&lt;q;++i){
            scanf("%d%d",&amp;l,&amp;r);
            printf("%d\n",queryMin(l-1,r-1));
        }
    }
    return 0;
}</code></pre>
<h2 id="toc-4">By：Wahacer</h2>
<h4 id="toc-5">资料来源：<a href="http://www.cnblogs.com/linkzijun/p/6347769.html">ST表博客</a></h4>
<p>2017年9月23号</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>